#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 100

typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

typedef struct AdjList {
    AdjListNode* head;
} AdjList;

typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;

    graph->array = (AdjList*)malloc(V * sizeof(AdjList));

    int i;
    for (i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}

bool visited[MAX_VERTICES];

bool hasPath(Graph* graph, int src, int dest) {
    visited[src] = true;

    AdjListNode* pCrawl = graph->array[src].head;

    while (pCrawl) {
        int v = pCrawl->dest;

        if (v == dest)
            return true;

        if (!visited[v] && hasPath(graph, v, dest))
            return true;

        pCrawl = pCrawl->next;
    }

    visited[src] = false;

    return false;
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);

    int src = 0, dest = 4;

    if (hasPath(graph, src, dest))
        printf("存在从顶点 %d 到顶点 %d 的路径\n", src, dest);
    else
        printf("不存在从顶点 %d 到顶点 %d 的路径\n", src, dest);

    return 0;
}